package tree.leetcode_124_hard;

public class MaxPathSum {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(-10);
        root.left = new TreeNode(9);
        root.right = new TreeNode(15);
        root.right.left = new TreeNode(20);
        root.right.right = new TreeNode(7);
        root.right.left.left = new TreeNode(8);
        System.out.println(maxPathSum(root));
    }

    /*
        必须使用全局变量，来记录最大路径值，递归中不断更新这个值

        为什么要使用系统最小值作为初始值，而不是0
            因为最大路径和可能为负数。
     */
    private static int maxSum = Integer.MIN_VALUE;
    public static int maxPathSum(TreeNode root){
        getMaxPathSum(root);
        return maxSum;
    }
    public static int getMaxPathSum(TreeNode root){
        //节点为null，路径值为0
        if(root == null){
            return 0;
        }
        //情况1 ：计算当前节点左孩子的最大路径值，如果左孩子为负数，为负增长，不如设置为0
        int leftPathSum = Math.max(0,getMaxPathSum(root.left));
        //情况2 ：计算当前节点右孩子的最大路径值，如果右孩子为负数，为负增长，不如设置为0
        int rightPathSum = Math.max(0,getMaxPathSum(root.right));

        //情况3 ：记录当前节点的路径值，当前节点的路径值 = 左 + 右 + 根
        int MaxPathSum = root.val + leftPathSum + rightPathSum;

        //记录当前节点的路径值，在递归过程中不断更新这个值，作为最后的结果。
        //这样设计的原因在于，最大路径不一定经过根节点，有可能最大路径和产生在左右的子树中，利用此变量来记录每一颗子树所产生的最大路径值，取最大的。
        maxSum = Math.max(maxSum,MaxPathSum);

        //告诉当前节点，它走的是那一边，要走路径大的那一边。
        return root.val + Math.max(leftPathSum,rightPathSum);
    }
}
